{ "cells": [ { "cell_type": "markdown", "source": [ "# Spellman's Distribution Network Optimization\n", "Spellman's would like Sabrina to focus on the optimization of their distribution network, to support the distribution of the 2 types of drinks from 3 sourcing facilities to 4 destination warehouses, through 6 intermediate warehouses. Sabrina needs to take into account the transportation costs (both from sourcing warehouses to intermediate warehouses and from intermediate warehouses to final destinations). Additionally, Sabrina can decide how many of the 6 intermediate solutions to use, given that they have a fixed operational cost that needs to be paid when the warehouse is used.\n", "\n", "The following tables contain the transportation problem data:\n", "\n", "### Capacities of Sourcing Facilities (in units)\n", "\n", "| Sourcing Warehouse | Product A Capacity (units) | Product B Capacity (units) |\n", "|--------------------|----------------------------|----------------------------|\n", "| S1 | 300 | 400 |\n", "| S2 | 250 | 150 |\n", "| S3 | 350 | 250 |\n", "\n", "### Demands at Final Destinations (in units)\n", "\n", "| Destination Warehouse | Product A Demand (units) | Product B Demand (units) |\n", "|-----------------------|--------------------------|--------------------------|\n", "| D1 | 150 | 150 |\n", "| D2 | 200 | 250 |\n", "| D3 | 175 | 175 |\n", "| D4 | 225 | 175 |\n", "\n", "\n", "#### Sourcing to Intermediate Warehouses Transportation Costs (Euros)\n", "\n", "| From/To | I1 | I2 | I3 | I4 | I5 | I6 |\n", "|---------|----|----|----|----|----|----|\n", "| S1 | 2 | 4 | 5 | 7 | 3 | 6 |\n", "| S2 | 3 | 2 | 6 | 8 | 4 | 5 |\n", "| S3 | 1 | 3 | 4 | 6 | 5 | 7 |\n", "\n", "#### Intermediate to Destination Warehouses Transportation Costs (Euros)\n", "\n", "| From/To | D1 | D2 | D3 | D4 |\n", "|---------|----|----|----|----|\n", "| I1 | 5 | 2 | 3 | 4 |\n", "| I2 | 4 | 1 | 5 | 2 |\n", "| I3 | 3 | 4 | 2 | 5 |\n", "| I4 | 5 | 3 | 4 | 1 |\n", "| I5 | 2 | 5 | 3 | 4 |\n", "| I6 | 4 | 2 | 1 | 5 |\n", "\n", "### Operational Costs of Intermediate Warehouses (Euros)\n", "\n", "| Warehouse | Operational Cost |\n", "|-----------|------------------|\n", "| I1 | 1000 |\n", "| I2 | 800 |\n", "| I3 | 1200 |\n", "| I4 | 1100 |\n", "| I5 | 700 |\n", "| I6 | 900 |\n", "\n", "Note that the distribution costs are independent of the product type.\n", "\n", "1. Help Sabrina write an Integer Programming Problem to model the transportation problem .\n", "\n", "**Index**\n", "- $i$: Index of the sourcing warehouse\n", "- $j$: Index of the intermediate warehouse\n", "- $k$: Index of the destination warehouse\n", "- $l$: Index of the product type\n", "\n", "**Decision variables**\n", "- $x_{ijl}$: Number of units of product $l$ transported from sourcing warehouse $i$ to intermediate warehouse $j$ (Integer)\n", "- $y_{jkl}$: Number of units of product $l$ transported from intermediate warehouse $j$ to destination warehouse $k$ (Integer)\n", "- $Z_{j}$: Binary variable indicating if intermediate warehouse $j$ is used (Binary)\n", "\n", "\n", "**Objective function**\n", "$\\min z = \\sum_{j} Z_{j} * F_{j} + \\sum_{i} \\sum_{j} \\sum_{l} s_{ijl} * x_{ijl} + \\sum_{j} \\sum_{k} \\sum_{l} t_{jkl} * y_{jkl}$\n", "\n", "Where:\n", "- $F_{j}$ is the operational cost of intermediate warehouse $j$. $F = [F_{1}, F_{2}, F_{3}, F_{4}, F_{5}, F_{6}] = [1000, 800, 1200, 1100, 700, 900]$\n", "- $s_{ijl}$ is the transportation cost from sourcing warehouse $i$ to intermediate warehouse $j$ for product $l$. The transportation costs do not depend on the product type and are indicated in the table above.\n", "- $t_{jkl}$ is the transportation cost from intermediate warehouse $j$ to destination warehouse $k$ for product $l$. The transportation costs do not depend on the product type and are indicated in the table above.\n", "\n", "**Constraints**\n", "- Sourcing capacity constraints:\n", "$\\sum_{j} x_{ijl} \\leq C_{il} \\quad \\forall i \\quad \\forall l$\n", "\n", "Where $C_{il}$ is the capacity of sourcing warehouse $i$ for product $l$. The capacities are indicated in the table above.\n", "\n", "- Destination demand constraints:\n", "$\\sum_{j} y_{jkl} = D_{kl} \\quad \\forall k \\quad \\forall l$\n", "\n", "Where $D_{kl}$ is the demand of destination warehouse $k$ for product $l$. The demands are indicated in the table above.\n", "\n", "- Flow conservation constraints:\n", "\n", "$\\sum_{i} x_{ijl} = \\sum_{k} y_{jkl} \\quad \\forall j \\quad \\forall l$\n", "\n", "- Logical constraints:\n", "\n", "$\\sum_{i} x_{ijl} \\leq M * Z_{j} \\quad \\forall j$\n", "\n", "\n", "2. How would a Greedy algorithm solve the problem? Motivate your response\n", "\n", "A greedy algorithm would solve the problem by making a series of decisions that are locally optimal at each step with the hope of finding a global optimum. The algorithm would start by selecting the intermediate warehouse with the lowest operational cost and then select the sourcing warehouse that minimizes the transportation cost to that intermediate warehouse. The algorithm would then select the destination warehouse that minimizes the transportation cost from the intermediate warehouse. This process would be repeated for each product type until all constraints are satisfied.\n", "\n", "The greedy algorithm is not guaranteed to find the optimal solution to the transportation problem. However, it is computationally efficient and can provide a good solution in a reasonable amount of time. The algorithm is particularly useful when the problem is large and complex, as it can quickly generate a feasible solution that can be used as a starting point for more sophisticated optimization techniques." ], "metadata": { "collapsed": false } } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" } }, "nbformat": 4, "nbformat_minor": 0 }